import math
i = int(input());
for j in range (0,i):
count=0
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
for y in range (0,n):
if a[y]%2==0:
a.insert(0,a.pop(y))
for k in range (0,n-1):
for x in range(k+1,n):
if math.gcd(a[k],2*a[x])>1:
count+=1
print(count)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
vector<int>vt(n);
int c=0;
for(int i=0;i<n;i++){
cin>>vt[i];
}
sort(vt.begin(), vt.end(), [](int x, int y) {
return x % 2 < y % 2;
});
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(__gcd(vt[i],2*vt[j])>1){
c++;
}
}
}
cout << c << endl;
}
return 0;
}2148. Count Elements With Strictly Smaller and Greater Elements | 2149. Rearrange Array Elements by Sign |
2150. Find All Lonely Numbers in the Array | 2151. Maximum Good People Based on Statements |
2144. Minimum Cost of Buying Candies With Discount | Non empty subsets |
1630A - And Matching | 1630B - Range and Partition |
1630C - Paint the Middle | 1630D - Flipping Range |
1328A - Divisibility Problem | 339A - Helpful Maths |
4A - Watermelon | 476A - Dreamoon and Stairs |
1409A - Yet Another Two Integers Problem | 977A - Wrong Subtraction |
263A - Beautiful Matrix | 180C - Letter |
151A - Soft Drinking | 1352A - Sum of Round Numbers |
281A - Word Capitalization | 1646A - Square Counting |
266A - Stones on the Table | 61A - Ultra-Fast Mathematician |
148A - Insomnia cure | 1650A - Deletions of Two Adjacent Letters |
1512A - Spy Detected | 282A - Bit++ |
69A - Young Physicist | 1651A - Playoff |